package net.apexes.commons.lang;

import java.io.ByteArrayOutputStream;
import java.nio.charset.StandardCharsets;

/**
 * A Base62 encoder/decoder.
 *
 * @author Sebastian Ruhleder, sebastian@seruco.io
 */
public final class Base62 {
    private Base62() {}

    private static final byte[] ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".getBytes(StandardCharsets.ISO_8859_1);
    private static final int STANDARD_BASE = 256;
    private static final int TARGET_BASE = 62;
    private static final byte[] LOOKUP;
    static {
        LOOKUP = new byte[256];
        for (int i = 0; i < ALPHABET.length; i++) {
            LOOKUP[ALPHABET[i]] = (byte) (i & 0xFF);
        }
    }

    /**
     * Encodes a sequence of bytes in Base62 encoding.
     *
     * @param message a byte sequence.
     * @return a sequence of Base62-encoded text.
     */
    public static String encode(final byte[] message) {
        final byte[] indices = convert(message, STANDARD_BASE, TARGET_BASE);
        return new String(translate(indices, ALPHABET), StandardCharsets.ISO_8859_1);
    }

    /**
     * Decodes a sequence of Base62-encoded bytes.
     *
     * @param encoded a sequence of Base62-encoded text.
     * @return a byte sequence.
     * @throws IllegalArgumentException when {@code encoded} is not encoded over the Base62 alphabet.
     */
    public static byte[] decode(String encoded) {
        return decode(encoded.getBytes(StandardCharsets.ISO_8859_1));
    }

    private static byte[] decode(byte[] encoded) {
        if (!isBase62Encoding(encoded)) {
            throw new IllegalArgumentException("Input is not encoded correctly");
        }
        final byte[] prepared = translate(encoded, LOOKUP);
        return convert(prepared, TARGET_BASE, STANDARD_BASE);
    }

    /**
     * Checks whether a sequence of bytes is encoded over a Base62 alphabet.
     *
     * @param bytes a sequence of bytes.
     * @return {@code true} when the bytes are encoded over a Base62 alphabet, {@code false} otherwise.
     */
    public static boolean isBase62Encoding(final byte[] bytes) {
        if (bytes == null) {
            return false;
        }
        for (final byte e : bytes) {
            if ('0' > e || '9' < e) {
                if ('a' > e || 'z' < e) {
                    if ('A' > e || 'Z' < e) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    /**
     * Uses the elements of a byte array as indices to a dictionary and returns the corresponding values
     * in form of a byte array.
     */
    private static byte[] translate(final byte[] indices, final byte[] dictionary) {
        final byte[] translation = new byte[indices.length];
        for (int i = 0; i < indices.length; i++) {
            translation[i] = dictionary[indices[i]];
        }
        return translation;
    }

    /**
     * Converts a byte array from a source base to a target base using the alphabet.
     */
    private static byte[] convert(final byte[] message, final int sourceBase, final int targetBase) {
        // This algorithm is inspired by: http://codegolf.stackexchange.com/a/21672
        final int estimatedLength = estimateOutputLength(message.length, sourceBase, targetBase);
        final ByteArrayOutputStream out = new ByteArrayOutputStream(estimatedLength);
        byte[] source = message;
        while (source.length > 0) {
            final ByteArrayOutputStream quotient = new ByteArrayOutputStream(source.length);
            int remainder = 0;
            for (byte b : source) {
                final int accumulator = (b & 0xFF) + remainder * sourceBase;
                final int digit = (accumulator - (accumulator % targetBase)) / targetBase;
                remainder = accumulator % targetBase;
                if (quotient.size() > 0 || digit > 0) {
                    quotient.write(digit);
                }
            }
            out.write(remainder);
            source = quotient.toByteArray();
        }

        // pad output with zeroes corresponding to the number of leading zeroes in the message
        for (int i = 0; i < message.length - 1 && message[i] == 0; i++) {
            out.write(0);
        }

        return reverse(out.toByteArray());
    }

    /**
     * Estimates the length of the output in bytes.
     */
    private static int estimateOutputLength(int inputLength, int sourceBase, int targetBase) {
        return (int) Math.ceil((Math.log(sourceBase) / Math.log(targetBase)) * inputLength);
    }

    /**
     * Reverses a byte array.
     */
    private static byte[] reverse(final byte[] arr) {
        final int length = arr.length;
        final byte[] reversed = new byte[length];
        for (int i = 0; i < length; i++) {
            reversed[length - i - 1] = arr[i];
        }
        return reversed;
    }

}
